//class Solution {
//public:
//    int massage(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 0) return 0;
//        vector<int> f(n);
//        vector<int> g(n);
//        f[0] = nums[0];
//        g[0] = 0;
//        for (int i = 1; i < n; i++)
//        {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n - 1], g[n - 1]);
//    }
//};

//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        if (nums.size() == 1) return nums[0];
//        if (nums.size() == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
//        int x = func1(nums);
//        x += nums[0];
//        int y = func2(nums);
//        return max(x, y);
//    }
//    int func1(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        f[2] = nums[2];
//        g[2] = 0;
//        for (int i = 2; i < n - 1; i++)
//        {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n - 2], g[n - 2]);
//    }
//    int func2(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        f[1] = nums[1];
//        g[1] = 0; // g[0] = 0;
//        for (int i = 1; i < n; i++)
//        {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n - 1], g[n - 1]);
//    }
//};

//class Solution {
//public:
//    int deleteAndEarn(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        int end = nums[nums.size() - 1];
//        vector<int> arr(end + 1);
//        unordered_map<int, int> hash;
//        for (auto& e : nums) hash[e]++;
//        for (int i = 0; i < arr.size(); i++)
//        {
//            arr[i] = hash[i] * i;
//        }
//        //
//        int n = arr.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        f[0] = arr[0];
//        g[0] = 0;
//        for (int i = 1; i < n; i++)
//        {
//            f[i] = g[i - 1] + arr[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n - 1], g[n - 1]);
//    }
//};

